package com.bittech.ds;

/**
 * @Author: yuisama
 * @Date: 2019-07-15 16:05
 * @Description:Java实现七大排序
 */
public class SortAlgorithm {
    private SortAlgorithm() {}
    //冒泡排序
    public static void bubbleSort(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return;
        }
        for (int i = 0; i < n; i++) {
            // 是否有元素交换
            boolean flag = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j+1]) {
                    flag = true;
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            // 本次循环已经没有元素交换了，冒泡结束
            if (!flag) {
                return;
            }
        }
    }
    // 直接插入排序
    public static void insertSort(int[] array) {
        int n = array.length;
        if (n <= 1)
            return;
        // 开始认为第一个元素为有序集合
        for (int i = 1; i < n; i++) {
            int value = array[i];
            int j = i - 1;
            // 从已排序集合中查找插入位置
            for(;j >= 0; j--) {
                if (array[j] > value)
                    // 元素搬移
                    array[j + 1] = array[j];
                else
                    break;
            }
            // 此时j+1对应下标即为需要插入的位置
            array[j + 1] = value;
        }
    }
    // 折半插入排序
    public static void binaryInsertSort(int[] array) {
        int n = array.length;
        if (n <= 1)
            return;
        int low,high,mid = 0;
        for (int i = 1; i < n; i++) {
            // 未排序集合的第一个元素
            int value = array[i];
            // low为已排序集合的第一个元素
            low = 0;
            // high为已排序集合的最后一个元素
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (array[mid] < value) {
                    low = mid + 1;
                }else
                    high = mid - 1;
            }
            // 此时high+1即为需要插入的位置
            for (int j = i - 1;j > high;j--)
                array[j + 1] = array[j];
            array[high + 1] = value;
        }
    }
    // 选择排序
    public static void selectSort(int[] array) {
        int n = array.length;
        if (n <= 1)
            return;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            // 此时minIndex为未排序数组的最小元素索引
            // 与已排序集合最后元素交换
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}
